package com.kobe.game_60;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import com.kobe.util.MathUtil;

/**
 * 
 * By replacing the 1^(st) digit of *3, it turns out that six of the nine
 * possible values: 13, 23, 43, 53, 73, and 83, are all prime.
 * 
 * By replacing the 3^(rd) and 4^(th) digits of 56**3 with the same digit, this
 * 5-digit number is the first example having seven primes among the ten
 * generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663,
 * 56773, and 56993. Consequently 56003, being the first member of this family,
 * is the smallest prime with this property.
 * 
 * Find the smallest prime which, by replacing part of the number (not
 * necessarily adjacent digits) with the same digit, is part of an eight prime
 * value family.
 * 
 */
public class _51 {
    public static List<int[]> getNoConflictPerms(int digit) {
        int[] originalPerm = new int[digit];
        List<int[]> returnPerms = new ArrayList<int[]>();
        // digit minus one for exclude all 1 situation
        for (int i = 0; i < digit - 1; i++) {
            if (digit >= 4 && i == 0) {
                originalPerm[i] = 1;
                continue;
            }
            originalPerm[i] = 1;
            returnPerms.addAll(getNoConflictPerms(MathUtil
                    .getPerm(originalPerm)));
        }
        return returnPerms;
    }

    public static List<int[]> getNoConflictPerms(List<int[]> perms) {
        List<int[]> returnPerms = new ArrayList<int[]>();
        out: for (int[] temp : perms) {
            for (int i = 0; i < returnPerms.size(); i++) {
                if (Arrays.equals(temp, returnPerms.get(i))) {
                    continue out;
                }
            }
            returnPerms.add(temp);
        }
        return returnPerms;
    }

    private static final int REPLACE_MARK = 1;

    private static int invadeArray(int[] resource, int target) {
        int base = -1;
        int returnValue = 0;
        int tempNumbe = 0;
        int tempTarget = target;

        boolean finishInvade = true;
        for (int i = resource.length - 1; i >= 0; i--) {

            if (resource[i] == 1) {
                if (base == -1) {
                    base = tempTarget % 10;
                    tempNumbe = REPLACE_MARK;
                    tempTarget /= 10;
                } else if (base == tempTarget % 10) {
                    tempNumbe = REPLACE_MARK;
                    tempTarget /= 10;
                } else {
                    finishInvade = false;
                    break;
                }
            } else {
                tempNumbe = tempTarget % 10;
                tempTarget /= 10;
            }
            returnValue += tempNumbe * Math.pow(10, resource.length - i - 1);
        }
        return finishInvade ? returnValue : target;
    }

    public static int[] findSamePrimes(int[] primes, int required, int digit) {

        List<int[]> resource = getNoConflictPerms(digit);
        int[] invadedPrimes = new int[primes.length];
        int[] invadedPrimesClone = null;
        int[] returnSamePrimes = new int[required];

        int base = 0;
        int found = 0;
        int foundPrimes = 0;
        boolean founded = false;

        out: for (int[] tempResource : resource) {
            System.out.println("executing: " + getArrayValue(tempResource));
            for (int i = 0; i < primes.length; i++) {
                invadedPrimes[i] = invadeArray(tempResource, primes[i]);
            }
            invadedPrimesClone = invadedPrimes.clone();
            Arrays.sort(invadedPrimes);
            for (int temp : invadedPrimes) {
                if (base != temp) {
                    base = temp;
                    found = 1;
                } else if (base == temp) {
                    found++;
                }
                if (found == required) {
                    foundPrimes = temp;
                    founded = true;
                    break out;
                }
            }
        }

        if (founded) {
            for (int i = 0, index = 0; i < invadedPrimesClone.length; i++) {
                if (foundPrimes == invadedPrimesClone[i]) {
                    returnSamePrimes[index++] = primes[i];
                }
            }
        }

        return founded ? returnSamePrimes : null;
    }

    static StringBuilder sb = new StringBuilder();

    public static String getArrayValue(int[] numbers) {
        sb.delete(0, sb.length());
        for (int temp : numbers) {
            sb.append(temp);
            sb.append(" ");
        }
        return sb.toString();
    }

    private static void cleanArray(int[] array) {
        for (int i = 0; i < array.length; i++)
            array[i] = 0;
    }

    public static void main(String[] args) {
        int[] primes = new int[90000];
        int[] returnValue;
        int bound = 100;

        long begin = System.currentTimeMillis();

        int required = 8;
        int digit = 2;
        for (int i = 11, index = 0;; i += 2) {
            if (MathUtil.isPrime(i)) {
                if (i >= bound) {
                    System.out.println("digit now: " + digit);
                    int[] dest = new int[index];
                    System.arraycopy(primes, 0, dest, 0, index);
                    returnValue = findSamePrimes(dest, required, digit);
                    if (returnValue != null) {
                        System.out.println(getArrayValue(returnValue));
                        break;
                    }
                    digit++;
                    bound *= 10;
                    cleanArray(primes);
                    index = 0;
                }
                primes[index++] = i;
            }
        }

        long end = System.currentTimeMillis();
        System.out.println("Used time: " + (end - begin));
    }
}
